
// Copyright (C) 2009-2011 Luca Piccioni
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//  
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//  
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Xml;
using System.Xml.Schema;
using System.Xml.Serialization;

namespace Derm.Scene
{
	/// <summary>
	/// Directed graph.
	/// </summary>
	/// <typeparam name="T">
	/// The type parameter <typeparamref name="T"/> shall derive src <see cref="DirectedGraphNode{T}"/>, allowing
	/// the definition of the arcs to other nodes.
	/// </typeparam>
	/// <remarks>
	/// A directed graph is defined as a set of nodes connected with a set of directed edges. In this implementation
	/// the directed graph has only one root node, and the nodes base implementation is determined src <typeparamref name="T"/>.
	/// </remarks>
	public class DirectedGraph<T> where T : DirectedGraphNode<T>
	{
		#region Root Node

		/// <summary>
		/// Directed graph root node.
		/// </summary>
		public T RootNode
		{
			get { return (mRootNode); }
			protected set { mRootNode = value; }
		}

		/// <summary>
		/// Directed graph root node.
		/// </summary>
		private T mRootNode;

		#endregion

		#region Graph Traversal

		/// <summary>
		/// 
		/// </summary>
		/// <param name="node"></param>
		/// <param name="data"></param>
		public delegate void NodeVisitorDelegate(T node, object data);

		/// <summary>
		/// Context used while traversing the DirectedGraph
		/// </summary>
		public class TraversalContext
		{
			/// <summary>
			/// Delegate called when a DirectedGraphNode is visited.
			/// </summary>
			public NodeVisitorDelegate VisitorDelegate;

			/// <summary>
			/// Delegate called after visiting each child of visited DirectedGraphNode.
			/// </summary>
			public NodeVisitorDelegate PostChildVisitDelegate;

			/// <summary>
			/// Delegate called after having visited all children of visited DirectedGraphNode.
			/// </summary>
			public NodeVisitorDelegate PostChildrenVisitDelegate;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="ctx"></param>
		/// <param name="data"></param>
		public void TraverseParentFirst(TraversalContext ctx, object data)
		{
			if (RootNode == null)
				return;

			TraverseParentFirst(RootNode, ctx, data);
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="node"></param>
		/// <param name="ctx"></param>
		/// <param name="data"></param>
		protected static void TraverseParentFirst(T node, TraversalContext ctx, object data)
		{
			if (node == null)
				throw new ArgumentNullException("node");
			if (ctx == null)
				throw new ArgumentNullException("ctx");
			if (ctx.VisitorDelegate == null)
				throw new ArgumentException("no visitor function", "ctx");

			// Visit node
			ctx.VisitorDelegate(node, data);

			// Visit node's children
			foreach (T child in node.Children) {
				// Resurse traversal on child
				TraverseParentFirst(child, ctx, data);
				// Post child visit
				if (ctx.PostChildVisitDelegate != null)
					ctx.PostChildVisitDelegate(node, data);
			}

			// Post children visit
			if (ctx.PostChildrenVisitDelegate != null)
				ctx.PostChildrenVisitDelegate(node, data);
		}

		#endregion
	}
}
